home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 11 / Cream of the Crop 11-1.iso / windows / boyer04.zip / BOYER.C next >
C/C++ Source or Header  |  1996-01-15  |  11KB  |  420 lines
  1. /*-----------------------------------------------------------------------------
  2.     file:   boyer.c
  3.     desc:   Boyer-Moore text search algorithm (Windows version)
  4.     by:     Patrick Ko
  5.     date:   6 Mar 91 - born
  6.     revi:   4 Apr 94 - port Windows 3.1
  7.             21 Aug 94 - support Windows DLL
  8.             13 Jan 95 v0.4 - bug fix FindIC() and FindBackwardIC()
  9.     note:   use huge pointers to cater for big contiguous memory
  10. -----------------------------------------------------------------------------*/
  11.  
  12. /*-----------------------------------------------------------------------------
  13.     Program Specification
  14.  
  15.     in:     search space s, pattern p
  16.     out:    a pointer where p is exactly matched at s[i], NULL indicates fail
  17.     why:    Boyer-Moore algorithm is best for general text search. On
  18.             "average" it takes length(s)/length(p) steps to match p in s.
  19.  
  20.     ref:    I recommend the following references:
  21.  
  22.             "Algorithms". Robert Sedgewick. Addison Wesley Publishing Company.
  23.             1988. 2nd addition. p286. QA76.6.S435 1983
  24.  
  25.             "Faster String Searches". Doctor Dobb's Journal. Volume 14
  26.             Issue 7 July 1989. Costas Menico. p74.
  27.  
  28.     usage:  e.g. to find a pattern "tiger" in a text in RAM starting at
  29.                  pointer "txtp" with a length of 1,000,000 characters,
  30.                  program like this:
  31.  
  32.             LPSTR matchp;
  33.  
  34.             SetFindPattern( "tiger" );
  35.             matchp = Find( txtp, 1000000L );
  36.             if (matchp != NULL)
  37.                 // found
  38.             else
  39.                 // not found
  40.  
  41.             matchp = FindBackward( txtp + 1000000L - 1, 1000000L);
  42.             if (matchp != NULL)
  43.                 // found
  44.             else
  45.                 // not found
  46.  
  47.  
  48.     Q:      Can I use Find() with a GlobalLock() pointer in Windows?
  49.     A:      Yes.
  50.  
  51.     Q:      Must I delcare my pointer as HPSTR (huge pointer) ?
  52.     A:      Not necessary.  Find() and FindBackward() will convert your
  53.             LPSTR as HPSTR.  However, in your own code you must aware
  54.             that you are holding a LPSTR and take care of the pointer
  55.             arithmetic and conversion. (see demo.c for example)
  56.  
  57.     Q:      What is the limit of the memory space I can search?
  58.     A:      To the limit of huge pointer implementation and your hardware.
  59.  
  60. -----------------------------------------------------------------------------*/
  61.  
  62. #include <windows.h>
  63. #include <ctype.h>
  64. #include "boyer.h"
  65.  
  66. #ifdef BOYERDLL
  67.  
  68. UINT WINAPI WEP(int nParam)
  69. {
  70.     nParam;
  71.     return 1;
  72. }
  73.  
  74. int FAR PASCAL LibMain(
  75.     HANDLE hInstance, UINT wDataSeg, UINT cbHeapSize, LPSTR lpszCmdLine)
  76. {
  77.     wDataSeg;
  78.     lpszCmdLine;
  79.  
  80.     if (!cbHeapSize)
  81.         return 0;
  82.  
  83.     UnlockData(0);
  84.     return 1;
  85. }
  86.  
  87. #endif
  88.  
  89.  
  90. /*-----------------------------------------------------------------------------
  91.     func:   SetFindPattern
  92.     desc:   initialize the pattern to be matched and generate skip table
  93.     pass:   lpszPattern = pattern string
  94.     rtrn:   HFIND - the find handle for further text search
  95. -----------------------------------------------------------------------------*/
  96. #ifdef BOYERDLL
  97. HFIND FAR PASCAL SetFindPattern( LPSTR lpszPattern )
  98. #else
  99. HFIND SetFindPattern( LPSTR lpszPattern )
  100. #endif
  101. {
  102.     register unsigned int j;
  103.     register char c;
  104.     HFIND hfind;
  105.     LPFIND lpfind;
  106.  
  107.     hfind = GlobalAlloc(GHND, sizeof(FINDSTRUCT));
  108.     if ((lpfind = (LPFIND)GlobalLock(hfind)) == NULL)
  109.         return NULL;
  110.  
  111.     lpfind->plen = lstrlen( lpszPattern );
  112.  
  113.     if (lpfind->plen > MAXPAT)
  114.         lpfind->plen = MAXPAT;
  115.  
  116.     lstrcpy( (LPSTR)(lpfind->p), lpszPattern );
  117.     lstrcpy( (LPSTR)(lpfind->pIC), lpszPattern );
  118.  
  119.     for (j=0; j<256; j++)
  120.     {
  121.         lpfind->skip[j] = lpfind->skipIC[j] = lpfind->plen;
  122.         lpfind->skipb[j] = lpfind->skipbIC[j] = lpfind->plen;
  123.     }
  124.  
  125.     for (j=0; j<lpfind->plen; j++)
  126.     {
  127.         lpfind->pIC[j] = toupper(lpfind->pIC[j]);
  128.         c = lpszPattern[j];
  129.         lpfind->skip[c] = lpfind->skipIC[toupper(c)] = lpfind->plen - j - 1;
  130.         lpfind->skipb[c] = lpfind->skipbIC[toupper(c)] = j;
  131.     }
  132.  
  133.     GlobalUnlock(hfind);
  134.     return (hfind);
  135. }
  136.  
  137. /*-----------------------------------------------------------------------------
  138.     func:   FreeFindPattern
  139.     desc:   free the memory occupied by SetFindPattern
  140.     pass:   hfind - the find handle
  141.     rtrn:   nothing
  142. -----------------------------------------------------------------------------*/
  143. #ifdef BOYERDLL
  144. void FAR PASCAL FreeFindPattern( HFIND hfind )
  145. #else
  146. void FreeFindPattern( HFIND hfind )
  147. #endif
  148. {
  149.     GlobalFree(hfind);
  150. }
  151.  
  152. /*-----------------------------------------------------------------------------
  153.     func:   Find
  154.     desc:   match a pattern defined in SetFindPattern against string s
  155.     pass:   hfind = the find handle created by SetFindPattern
  156.             s = start of search space, slen = length of s
  157.     rtrn:   NULL = match fail
  158.             else = a LPSTR to p[0] in s matches p
  159. -----------------------------------------------------------------------------*/
  160. #ifdef BOYERDLL
  161. LPSTR FAR PASCAL Find( HFIND hfind, LPSTR s, LONG slen )
  162. #else
  163. LPSTR Find( HFIND hfind, LPSTR s, LONG slen )
  164. #endif
  165. {
  166.     LONG i;
  167.     unsigned int n, j;
  168.     register char c;
  169.     LPFIND lpfind;
  170.     LPSTR lpresult;
  171.     HPSTR S;
  172.  
  173.     if ((lpfind = (LPFIND)GlobalLock(hfind)) == NULL)
  174.         return (NULL);
  175.  
  176.     i = j = lpfind->plen;
  177.     S = (HPSTR)s;
  178.  
  179.     do
  180.     {
  181.         c = *(S + (i - 1));
  182.  
  183.         if (c == lpfind->p[j - 1])
  184.         {
  185.             i--;
  186.             j--;
  187.         }
  188.         else
  189.         {
  190.             n = lpfind->plen - j + 1;
  191.             if (n > lpfind->skip[c] )
  192.             {
  193.                 i += n;
  194.             }
  195.             else
  196.             {
  197.                 i += lpfind->skip[c];
  198.             }
  199.             j = lpfind->plen;
  200.         }
  201.     }
  202.     while (j >= 1 && i <= slen);
  203.  
  204.     /* match fails */
  205.     if (i >= slen)
  206.     {
  207.         lpresult = (LPSTR)NULL;
  208.     }
  209.     /* match successful */
  210.     else
  211.     {
  212.         lpresult = S + i;
  213.     }
  214.  
  215.     GlobalUnlock(hfind);
  216.     return (lpresult);
  217. }
  218.  
  219. /*-----------------------------------------------------------------------------
  220.     func:   FindBackward
  221.     desc:   match a pattern defined in SetFindPattern against string s
  222.             in backward manner
  223.     pass:   hfind = the find handle created by SetFindPattern
  224.             s = start of search space, slen = length of s
  225.     rtrn:   NULL = match fail
  226.             else = a LPSTR to p[0] in s matches p
  227. -----------------------------------------------------------------------------*/
  228. #ifdef BOYERDLL
  229. LPSTR FAR PASCAL FindBackward( HFIND hfind, LPSTR s, LONG slen )
  230. #else
  231. LPSTR FindBackward( HFIND hfind, LPSTR s, LONG slen )
  232. #endif
  233. {
  234.     LONG i;
  235.     unsigned int n, j;
  236.     register char c;
  237.     LPFIND lpfind;
  238.     LPSTR lpresult;
  239.     HPSTR S;
  240.  
  241.     if ((lpfind = (LPFIND)GlobalLock(hfind)) == NULL)
  242.         return (NULL);
  243.  
  244.     i = j = lpfind->plen;
  245.     S = (HPSTR)s;
  246.  
  247.     do
  248.     {
  249.         c = S[1 - i];
  250.         if (c == lpfind->p[lpfind->plen - j])
  251.         {
  252.             i--;
  253.             j--;
  254.         }
  255.         else
  256.         {
  257.             n = lpfind->plen - j + 1;
  258.             if (n > lpfind->skipb[c])
  259.             {
  260.                 i += n;
  261.             }
  262.             else
  263.             {
  264.                 i += lpfind->skipb[c];
  265.             }
  266.             j = lpfind->plen;
  267.         }
  268.     }
  269.     while (j >= 1 && i <= slen);
  270.  
  271.     /* match fails */
  272.     if (i >= slen)
  273.     {
  274.         lpresult = (LPSTR)NULL;
  275.     }
  276.     /* match successful */
  277.     else
  278.     {
  279.         lpresult = (LPSTR)(S - i - lpfind->plen + 1);
  280.     }
  281.  
  282.     GlobalUnlock(hfind);
  283.     return (lpresult);
  284. }
  285.  
  286. /*-----------------------------------------------------------------------------
  287.     func:   FindIC
  288.     desc:   match a pattern defined in SetFindPattern against string s
  289.             and Ignore Case (i.e. case insensitive)
  290.     pass:   hfind = the find handle created by SetFindPattern
  291.             s = start of search space, slen = length of s
  292.     rtrn:   NULL = match fail
  293.             else = a LPSTR to p[0] in s matches p
  294. -----------------------------------------------------------------------------*/
  295. #ifdef BOYERDLL
  296. LPSTR FAR PASCAL FindIC( HFIND hfind, LPSTR s, LONG slen )
  297. #else
  298. LPSTR FindIC( HFIND hfind, LPSTR s, LONG slen )
  299. #endif
  300. {
  301.     LONG i;
  302.     unsigned int n, j;
  303.     register char c;
  304.     LPFIND lpfind;
  305.     LPSTR lpresult;
  306.     HPSTR S;
  307.  
  308.     if ((lpfind = (LPFIND)GlobalLock(hfind)) == NULL)
  309.         return (NULL);
  310.  
  311.     i = j = lpfind->plen;
  312.     S = (HPSTR)s;
  313.  
  314.     do
  315.     {
  316.         c = toupper(S[i - 1]);
  317.         if (c == lpfind->pIC[j - 1])
  318.         {
  319.             i--;
  320.             j--;
  321.         }
  322.         else
  323.         {
  324.             n = lpfind->plen - j + 1;
  325.             if (n > lpfind->skipIC[c])
  326.             {
  327.                 i += n;
  328.             }
  329.             else
  330.             {
  331.                 i += lpfind->skipIC[c];
  332.             }
  333.             j = lpfind->plen;
  334.         }
  335.     }
  336.     while (j >= 1 && i <= slen);
  337.  
  338.     /* match fails */
  339.     if (i >= slen)
  340.     {
  341.         lpresult = (LPSTR)NULL;
  342.     }
  343.     /* match successful */
  344.     else
  345.     {
  346.         lpresult = S + i;
  347.     }
  348.  
  349.     GlobalUnlock(hfind);
  350.     return (lpresult);
  351. }
  352.  
  353. /*-----------------------------------------------------------------------------
  354.     func:   FindBackwardIC
  355.     desc:   match a pattern defined in SetFindPattern against string s
  356.             in backward manner and ignore case (i.e. case insensitive)
  357.     pass:   hfind = the find handle created by SetFindPattern
  358.             s = start of search space, slen = length of s
  359.     rtrn:   NULL = match fail
  360.             else = a LPSTR to p[0] in s matches p
  361. -----------------------------------------------------------------------------*/
  362. #ifdef BOYERDLL
  363. LPSTR FAR PASCAL FindBackwardIC( HFIND hfind, LPSTR s, LONG slen )
  364. #else
  365. LPSTR FindBackwardIC( HFIND hfind, LPSTR s, LONG slen )
  366. #endif
  367. {
  368.     LONG i;
  369.     unsigned int n, j;
  370.     register char c;
  371.     LPFIND lpfind;
  372.     LPSTR lpresult;
  373.     HPSTR S;
  374.  
  375.     if ((lpfind = (LPFIND)GlobalLock(hfind)) == NULL)
  376.         return (NULL);
  377.  
  378.     i = j = lpfind->plen;
  379.     S = (HPSTR)s;
  380.  
  381.     do
  382.     {
  383.         c = toupper(S[1 - i]);
  384.         if (c == lpfind->pIC[lpfind->plen - j])
  385.         {
  386.             i--;
  387.             j--;
  388.         }
  389.         else
  390.         {
  391.             n = lpfind->plen - j + 1;
  392.             if (n > lpfind->skipbIC[c] )
  393.             {
  394.                 i += n;
  395.             }
  396.             else
  397.             {
  398.                 i += lpfind->skipbIC[c];
  399.             }
  400.             j = lpfind->plen;
  401.         }
  402.     }
  403.     while (j >= 1 && i <= slen);
  404.  
  405.     /* match fails */
  406.     if (i >= slen)
  407.     {
  408.         lpresult = (LPSTR)NULL;
  409.     }
  410.     /* match successful */
  411.     else
  412.     {
  413.         lpresult = (LPSTR)(S + 1 - i - lpfind->plen);
  414.     }
  415.  
  416.     GlobalUnlock(hfind);
  417.     return (lpresult);
  418. }
  419.  
  420.